1. Field of the Invention
This invention is related to layout of data structures and, in particular, to layout of data structures including bit-field data members.
2. Related Art
Computer programming languages generally support several types of data. For example, the C and C++ programming languages allow data to be of type "int" (integer number), "char" (character), "float" (real number) or "double" (double precision real number), among others. Related data is often collected together in a group. For example, in C and C++, the data (of any type) can be collected together into user-defined groups called "structs". Each item of data in a data structure is a "data member".
In C and C++, the data types listed above are called "basic types". (Other data types, such as arrays, also exist. Even a data structure can be a data type, i.e., a data structure can be a data member within another data structure.) Generally, associated with each basic type of data is a predefined number of bits of memory ("basic type size") for storing a data member of that type. Generally, the basic type size depends upon the architecture of the computer that is used for processing the data. For example, on most computers, the basic type size of the "int" basic type is 32 bits (4 bytes) and the basic type size of the "char" basic type is 8 bits (1 byte).
In addition to the above-listed basic types, C and C++ (as well as other programming languages) support another group of data types, called "bit-fields". Bit-fields are special cases of other basic types, bit-fields having a size that, unlike a typical basic type size, is not specified as a number of bytes, but rather as a number of bits that may or may not (typically, not) correspond to an exact number of bytes. Generally, bit-fields can have a size of any number of bits. Bit-fields can be of any integer scalar (i.e., subject to representation by a "count") basic type, such as "int", "short int", "long int", or "char". A data member may be specified as a bit-field, for example, when it is known that the data member will always require no more than a particular number of bits that is less than the number of bits of the basic type size of the corresponding basic type. A data member may also be specified as a bit-field, for example, to facilitate mapping of the data member to corresponding gobits of an external entity such as a control register of an I/O device.
In addition to defining the amount of memory allocated for storage of a data member, e.g., the basic type size, computer architecture can restrict the location of the beginning of each data member, i.e., the computer architecture defines an "alignment requirement" for each data member. Generally, the computer architecture defines an alignment requirement for each data type. For example, a 32-bit RISC CPU may require that all 32-bit data (e.g., data of type "int") begin on a 32-bit address boundary, i.e., at the first bit of the zeroth byte, the fourth byte, the eighth byte, etc. Or, a CPU (e.g., the Motorola 68000 processor) may require that such data begin on a 16-bit address boundary, i.e., at the first bit of the zeroth byte, the second byte, the fourth byte, etc. Further, some programming languages may place restrictions on the placement of data within a memory. For example, the C and C++ programming languages require that the address of each data member of a structure be higher than that of data members of the structure for which memory has previously been allocated.
"Data structure layout" is the process of allocating a portion of a memory for each data member of a data structure. Typically, this is done by defining the location in memory at which each data member begins. An initial address is established as the location of the beginning of a first data member of the data structure. The remaining data members are sequentially processed to determine a location of the beginning of each data member, expressed as an offset (data member offset) from the initial address.
In previous data structure layout methods, the data member offsets are determined, in the first instance, to adequately accommodate the size of each data member and to conform to the alignment requirement of the data type of each data member. To ensure that each data member is placed in memory at a location which satisfies the alignment requirement of the data member, unused bits ("padding bits") may be introduced between adjacent data members in memory. The largest alignment requirement of a data member of the data structure is defined as the alignment requirement of the data structure. After all data members are layed out, additional bits ("trailing bits") are added to the end of the data structure so that the size of the data structure is a multiple of the structure alignment requirement. This is done to ensure that, if the data structure is included in an array of other similar data structures, each of the data structures in the array will be properly aligned, i.e., conform to the structure alignment requirement.
Data structure layout for data structures including bit-field data members is more complicated than data structure layout for data structures that do not include bit-field data members. Most computer architectures allocate memory in bytes rather than in bits. Thus, a data structure layout method must account for the "non-standard" sizes (i.e., sizes not expressed in bytes) of the bit-field data members. Additionally, bit-field data members may be allocated to the unused portion of the allocation for a preceding data member. And, bit-field data members can begin at other than the beginning of a byte and end at other than the end of a byte.
Computer systems, particularly real-time or embedded systems, often impose particular constraints on the layout of the data structures of a computer program. For example, as indicated above, bit-field data members of a data structure may need to map to an I/O port layout or to a status register of the system. Further, it is desirable that the data structures of a computer program be capable of being layed out in a manner that is compatible with different computer systems so that data can be easily shared between the systems. For example, it is desirable that a data structure layout be compatible with different microprocessors having different data alignment requirements. Existing data structure layout methods have not adequately provided these capabilities.